package com.zhu.solution.writtenExamination;

import com.zhu.algorithm.sort.RandomArray;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2023/10/25/11:17
 * @Description: 从一亿个数据里找前N个最大/最小的数？
 *
 * 找前n个最大数，用小顶堆
 * 找前n个最小数，用大顶堆
 *
 */
public class findTopNNumbers {

    public static void main(String[] args) {

//        int[] sourceArray = {125, 585, 3, 44, 38, 5, 47, 15, 36, 25, 27, 2, 46, 4, 19, 50, 48, 45, 24, 35, 75, 458, 66, 98, 233};

        //当源数组有一万个元素时
        int[] sourceArray = new RandomArray().randomArray_1000000();

//        List<Integer> sourceList = Arrays.asList(sourceArray);
        List<Integer> sourceList = Arrays.stream(sourceArray).boxed().collect(Collectors.toList());

        List<Integer> topNMaxNumbers = new findTopNNumbers().findTopNMaxNumbers(sourceList,5);
        List<Integer> topNMinNumbers = new findTopNNumbers().findTopNMinNumbers(sourceList,5);

        System.out.println(topNMaxNumbers.toString());
        System.out.println(topNMinNumbers.toString());
    }


    /**
     * 找前n个最大数，用小顶堆
     * @param data
     * @param N
     * @return
     */
    public List<Integer> findTopNMaxNumbers(List<Integer> data, int N) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(N);

        for (int i = 0; i < N; i++) {
            minHeap.offer(data.get(i));
        }

        for (int i = N; i < data.size(); i++) {
            int current = data.get(i);
            if (current > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(current);
            }
        }

        List<Integer> result = new ArrayList<>(minHeap);
//        最终结果降序
//        Collections.sort(result, Collections.reverseOrder()); // Optional if you want the result in descending order
//        最终结果升序
        Collections.sort(result, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        return result;
    }

    /**
     * 找前n个最小数，用大顶堆
     * @param data
     * @param N
     * @return
     */
    public List<Integer> findTopNMinNumbers(List<Integer> data, int N) {

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(N, Collections.reverseOrder());

        for (int i = 0; i < N; i++) {
            maxHeap.offer(data.get(i));
        }

        for (int i = N; i < data.size(); i++) {
            int current = data.get(i);
            if (current < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(current);
            }
        }

        List<Integer> result = new ArrayList<>(maxHeap);
//        最终结果降序
//        Collections.sort(result, Collections.reverseOrder()); // Optional if you want the result in descending order
//        最终结果升序
        Collections.sort(result, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        return result;
    }







}
